Q: Double hashing is one of the best methods available for open addressing.
Solution: Double hashing is one of the best methods for open addressing because the permutations produced have many characteristics of randomly chosen permutations.
Q: What is the hash function used in Double Hashing?
Solution: Double hashing uses a hash function of the form (h1(k) + i*h2(k))mod m where h1 and h2 are auxiliary hash functions and m is the size of the hash table.
Q: On what value does the probe sequence depend on?
Solution: The probe sequence depends in upon the key k since the initial probe position, the offset or both may vary.
Q: The value of h2(k) can be composite relatively to the hash table size m.
Solution: The value h2(k) must be relatively prime to the hash table size m for the entire hash table to be searched. It can be ensured by having m in powers of 2 and designing h2 so that it produces an odd number.
Q: What are the values of h1(k) and h2(k) in the hash function?
Solution: The values h1(k) and h2(k) are k mod m and 1+(k mod m’) respectively where m is a prime number and m’ is chosen slightly less than m. (m’=m-1).
Q: What is the running time of double hashing?
Solution: The running time of double hashing is Theta(m) since each possible (h1(k), h2(k)) pair yields a distinct probe sequence. Hence the performance of double hashing is better.
Q: Which technique has the greatest number of probe sequences?
Solution: Double hashing has the greatest number of probe sequences thereby efficiently resolves hash collision problems.
Q: At what position the number 72 gets inserted in the following table? Index Key 0 22 1 34 2 3 4 5 56 6 7 18 8 41 9 10
Solution: The number 72 must be inserted at index 6. H(k)=k mod m H(72)= 72 mod 11 H(72)= 6.
Q: Where does the number 14 get inserted in the following table? Index Key 0 1 79 2 3 4 69 5 98 6 7 72 8 9 10 11 50 12
Solution: Here the hash table is of size 13 with h1(k) = k mod 13 and h2(k) = 1 + k mod 11. Since 14 = 1 (mod 13) and 14 = 3 (mod 11), the key 14 is inserted into empty slot 9.
Q: What is the value of m’ if the value of m is 19?
Solution: The value of m’ is chosen as a prime number slightly less than the value of m. Here the value of m is 19, hence the value of m’ can be chosen as 17.
You Have Score    | /10 |